package com.bee.剑指offer;

/**
 *
 */
public class 在二叉树中找到两个节点的最近公共祖先 {

    public int lowestCommonAncestor(TreeNode root, int o1, int o2) {
        TreeNode dfs = dfs(root, o1, o1);
        return dfs.val;
    }

    public TreeNode dfs(TreeNode root, int o1, int o2) {
        if (root == null) {
            return root;
        }
        if (root.val == o1 || root.val == o2) {
            return root;
        }
        TreeNode left = dfs(root.left, o1, o2);
        TreeNode right = dfs(root.right, o1, o2);
        // o1,o2分别在root节点的左右子树上
        if (left != null && right != null) {
            return root;
        }
        return left == null ? right : left;
    }

    public static TreeNode dfscd(TreeNode root,int o1,int o2) {
        if(root == null) {
            return null;
        }
        if(root.val == o1 || root.val == o2) {
            return root;
        }
        TreeNode left = dfscd(root.left, o1, o2);
        TreeNode right = dfscd(root.right,o1,o2);
        if(left != null && right != null) {
            return root;
        }
        return left == null ? right : left;
    }

    public static void main(String[] args) {

    }
}
